(1) Field of the Invention
The invention relates to the problem of scheduling traffic in a switch/router. More particularly, the invention relates to the problem of reducing switch latency for high priority, or real-time, traffic in a switch/router that uses a request/grant mechanism for traffic scheduling.
(2) Description of the Related Art
Communication networks typically use devices for directing the flow of data through them. Such devices are often characterized as switches and routers, which may be referred to collectively as switches/routers. A switch/router often needs to process data of different priorities according to different criteria. However, switches/routers often exhibit deficiencies that prevent them from maintain conformance with some of the particular criteria that may be desired.
Switch/routers commonly have a structure in which processing circuitry associated with ports to external lines is located on line cards, which may contain the ports and circuitry associated with one or more external lines. Among other functions, the circuitry determines the preferred destination of arriving packets. Packets are transmitted to the line card(s) associated with the preferred destination(s) by means of a switching fabric. To provide a high performance switch/router, it is necessary for the switch fabric to efficiently carry data between line cards with high data rates and low latency. In order to meet these requirements, an important class of switching fabric has emerged. It is characterized by a request/grant structure. Line cards request access to use a path through the fabric to carry data to the desired destination line card. An arbitrator associated with the switch fabric processes the requests from all line cards to determine a way to grant access to line cards to optimize fabric utilization and fairness and other criteria. Once the decision is made, access is granted to line cards to send data destined for a particular destination through the switch fabric at a particular time. The switch fabric is configured so that, at that particular time, data sent from selected inputs is transferred to selected outputs corresponding to the grants given. The latency between data being presented to the fabric and it arriving at the destination line cards is deterministic. Thus, no reordering of the data occurs within the switch fabric. Such a class of switch fabric presents an excellent example of a context to which at least one embodiment of the present invention may be beneficially applied.
FIG. 1 is a timing diagram illustrating a prior art technique for scheduling traffic in a communications node. Events occur at varying relative times along time access 101. Events are categorized as occurring during a request phase 102, the grant phase 103, and a data phase 104. During request phase 102, a line card generates requests and communicates them to a switch fabric. In the illustrated example, a line card first generates and communicates low priority (LP) request 105 then, at time 113, generates and communicates high priority (HP) requests 106.
At grant phase 103, the switch fabric grants opportunities for the line card to communicate the indicated data through the switch fabric. In the illustrated example, the switch fabric issues grant 107 corresponding to the low priority request 105 and high priority grant 108, which corresponds to high priority request 106 as shown by connection 111. However, in the illustrated example, high priority grant 108 occurs at time 114, which follows time 113 by a duration 115. Since certain latency requirements maybe placed upon high priority data, a limit may be placed on duration 115 between issuance of high priority request 106 at time 113 and issuance of high priority grant 108 at time 114. Under some circumstances, if high priority grant 108 occurs well after the issuance of high priority request 106, duration 15 may exceed such latency limits.
At data phase 104, the line card communicates the data associated with the granted requests from the line card to the switch fabric. In the illustrated example, data communication corresponding to the low priority request and grant occurs slightly after the issuance of low priority grant 107, and data communication 110 corresponding to the high priority request and grant occurs shortly after the issuance of grant 108, as illustrated by connection 112.
FIG. 1 shows an example prior art request/grant chronological sequence of low priority (LP) and high priority (HP) requests, grants and their associated data transmissions (e.g., an ATM cell).
Referring to FIG. 1, the flow of respective LP and HP request/grant/data occurrences are sequential in nature. Each request includes a priority indication, either high or low, an identifier, and a destination switch fabric output port indication (not shown). The request originates from a line card in a switch/router and is sent to a switch fabric of the switch/router for consideration. If the fabric can meet the request, typically for the transmission of one cell into the fabric, then it replies accordingly with a grant. The grant includes an indication of the same priority and identifier as the request. The line card receives the grant after some delay and then transmits the data to the switch fabric. For example, at time A a line card sends a HP request to the switch fabric, at time B the line card receives a grant in reply, and at time C the line card transmits the data to the fabric. Likewise, a similar flow occurs for an LP request sent prior to time A, with corresponding grant and data occurrences happening at times prior to times B and C, respectively.
Referring to FIG. 1, the time delay between a request and a grant received in reply can be greater than an allowable maximum delay limit for HP traffic, especially if the switch/router starts to become overloaded. Where the HP traffic carries real-time services this delay could result in an unacceptable degradation in service quality, and therefore would be desirable to avoid. Thus, a technique is needed to ensure that guaranteed bandwidth commitments are met while maximizing utilization of switching/routing capacity.
The use of the same reference symbols in different drawings indicates similar or identical items.